package DMSXL._2024.Graph;

import java.util.ArrayList;
import java.util.List;

public class allPathsSourceTarget {
    public static void main(String[] args) {
        int[][] graph = {{1,2},{3},{3},{}};
        System.out.println(new allPathsSourceTarget().allPathsSourceTarget(graph));
    }
    List<List<Integer>> ans;		// 用来存放满足条件的路径
    List<Integer> cnt;		// 用来保存 dfs 过程中的节点值

    public void dfs(int[][] graph, int node){
        if(node == graph.length - 1){
            ans.add(new ArrayList<>(cnt));
            return;
        }
        for (int index = 0; index < graph[node].length; index++) {
            int nextNode = graph[node][index];
            cnt.add(nextNode);
            dfs(graph,nextNode);
            cnt.remove(cnt.size() - 1);
        }
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        ans = new ArrayList<>();
        cnt = new ArrayList<>();
        cnt.add(0);			// 注意，0 号节点要加入 cnt 数组中
        dfs(graph, 0);
        return ans;
    }
}
